package cn.dapeng.array;

import cn.dapeng.sort.InsertSort;

import java.util.ArrayList;
import java.util.List;

/**
 * 对有序数组 二分查找
 */
public class BSExist {

    /**
     * 二分法查找
     *
     * @param array  : 必须是一个排好序的数组
     * @param target : 在数组中要寻找的数字
     * @return
     */
    public static boolean exist(int[] array, int target) {
        if (array == null || array.length == 0) return false;

        int left = 0, right = array.length - 1;
        while (left <= right) {
            int middle = (left + right) / 2;
            if (array[middle] == target) {
                return true;
            } else if (array[middle] < target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return false;
    }


    /**
     * 二分法查找, 找到所有匹配数字的下标
     *
     * @param array  : 必须是一个排好序的数组
     * @param target : 在数组中要寻找的数字
     * @return
     */
    public static List<Integer> find(int[] array, int target) {
        if (array == null || array.length == 0) return null;

        int left = 0, right = array.length - 1;
        List<Integer> result = new ArrayList<>();
        while (left <= right) {
            int middle = (left + right) / 2;
            if (array[middle] == target) {
                result.add(middle);
            } else if (array[middle] < target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return result;
    }

    /**
     * 对数期
     *
     * @param array
     * @param target
     * @return
     */
    public static boolean test(int[] array, int target) {
        if (array == null || array.length == 0) return false;

        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) {
                return true;
            }
        }
        return false;
    }


    /**
     * 创建一个随机数组，数组的取值范围在 minValue ~ maxValue之间 长度在 3 ~ maxLength -1 之间
     *
     * @param minValue  : 数组最小值
     * @param maxValue  : 数组最大值
     * @param maxLength : 数组最小长度
     * @param maxLength : 数组最大长度
     * @return
     */
    public static int[] builderSampleArray(int minValue, int maxValue, int minLength, int maxLength) {
        int length = 0;

        while (length < minLength) {
            length = (int) (Math.random() * maxLength);
        }

        int[] array = new int[length];

        for (int i = 0; i < length; i++) {
            array[i] = (int) (Math.random() * (maxValue - minValue) + minValue);
        }

        return array;
    }


    public static void main(String[] args) {

        int minValue = 5, maxValue = 100, testTime = 10000;

        for (int i = 0; i < testTime; i++) {
            int[] array = builderSampleArray(minValue, maxValue, 3, 20);
            InsertSort.sort(array);
            int target = (int) (Math.random() * (maxValue - minValue) + minValue);
            if (exist(array, target) != test(array, target)) {
                System.out.println("Oops");
            }
        }

    }
}
